home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Libraries / KPlib 1.3.5 / KPBag.h < prev    next >
Text File  |  1995-12-17  |  17KB  |  615 lines
  1. // A module of KPlib v1.3.5.
  2. // Written by Keith Pomakis during the summer of 1994.
  3. // Released to the public domain on October 10, 1994.
  4.  
  5. #ifndef KP_BAG_DEFINED
  6. #define KP_BAG_DEFINED
  7.  
  8. #include <stdlib.h>
  9. #include "KPbasic.h"
  10. #include "KPList.h"
  11.  
  12. // Assumes Element has a default constructor, operator=(), operator==(),
  13. // and operator<().  Note that operator<() must place a total ordering on
  14. // the Elements.
  15.  
  16. // KPBag<T>::operator<() places a total ordering on all KPBag<T> elements,
  17. // so that KPSet<KPBag<T> > is possible.
  18.  
  19. template <class Element>
  20. class KPBag {
  21.     public:
  22.         KPBag();
  23.         KPBag(const KPBag<Element> &bag);
  24.         KPBag(const KPList<Element> &list);
  25.         KPBag(const Element &element, int count=1);
  26.         ~KPBag();
  27.         operator KPList<Element>() const;
  28.  
  29.         KPBag<Element> operator+(const KPBag<Element> &bag) const;
  30.         KPBag<Element> operator+(const Element &element) const;
  31.         KPBag<Element> &operator+=(const KPBag<Element> &bag);
  32.         KPBag<Element> &operator+=(const Element &element);
  33.         KPBag<Element> &add(const KPBag<Element> &bag);
  34.         KPBag<Element> &add(const Element &element, int num=1);
  35.  
  36.         // It is illegal to call the following functions unless the elements
  37.         // are there to be removed!  If unsure, call contains() first.
  38.         KPBag<Element> operator-(const KPBag<Element> &bag) const;
  39.         KPBag<Element> operator-(const Element &element) const;
  40.         KPBag<Element> &operator-=(const KPBag<Element> &bag);
  41.         KPBag<Element> &operator-=(const Element &element);
  42.         KPBag<Element> &remove(const KPBag<Element> &bag);
  43.         KPBag<Element> &remove(const Element &element, int num=1);
  44.         KPBag<Element> &remove_all(const Element &element);
  45.  
  46.         // Miscellaneous
  47.         bool operator==(const KPBag<Element> &bag) const;
  48.         bool operator!=(const KPBag<Element> &bag) const;
  49.         bool operator<(const KPBag<Element> &bag) const;
  50.         KPBag<Element> &operator=(const KPBag<Element> &bag);
  51.         KPBag<Element> &operator=(const Element &element);
  52.         KPBag<Element> &operator=(const KPList<Element> &list);
  53.         KPList<Element> list() const;
  54.         KPList<Element> unique_list() const;
  55.         int size() const;        // Total number of elements.
  56.         int unique_size() const; // Total number of unique elements.
  57.         bool is_empty() const;
  58.         bool contains(const KPBag<Element> &bag) const;
  59.         bool contains(const Element &element, int num=1) const;
  60.         int occurrences_of(const Element &element) const;
  61.         Element retrieve();  // Returns and removes an element.
  62.         KPBag<Element> &clear();
  63.     protected:
  64.         class Slot {
  65.             public:
  66.                 Element my_element;
  67.                 int my_count;
  68.             public:
  69.                 Slot(): my_count(0)
  70.                     { /* do nothing */ }
  71.                 Slot(const Slot &slot): my_count(slot.my_count)
  72.                     {  my_element = slot.my_element; }
  73.                 Slot(const Element &element, int num): my_count(num)
  74.                     { my_element = element; }
  75.                 void operator=(const Slot &slot)
  76.                     { my_element = slot.my_element; my_count = slot.my_count; }
  77.         };
  78.         KPList<KPBag<Element>::Slot> my_list;
  79. };
  80.  
  81. /****************************************************************************/
  82.  
  83. template <class Element>
  84. inline
  85. KPBag<Element>::KPBag(): my_list()
  86. { /* do nothing */ }
  87.  
  88. /****************************************************************************/
  89.  
  90. template <class Element>
  91. inline
  92. KPBag<Element>::KPBag(const KPBag<Element> &bag): my_list(bag.my_list)
  93. { /* do nothing */ }
  94.  
  95. /****************************************************************************/
  96.  
  97. template <class Element>
  98. inline
  99. KPBag<Element>::KPBag(const KPList<Element> &list)
  100. {
  101.     *this = list;
  102. }
  103.  
  104. /****************************************************************************/
  105.  
  106. template <class Element>
  107. inline
  108. KPBag<Element>::KPBag(const Element &element, int count): my_list()
  109. {
  110.     if (count < 0) {
  111.         cerr << "KPBag - negative count\n";
  112.         exit(EXIT_FAILURE);
  113.     }
  114.     else if (count > 0) {
  115.         KPBag<Element>::Slot slot(element, count);
  116.         my_list = slot;
  117.     }
  118. }
  119.  
  120. /****************************************************************************/
  121.  
  122. template <class Element>
  123. inline
  124. KPBag<Element>::~KPBag()
  125. {
  126.     my_list.clear();
  127. }
  128.  
  129. /****************************************************************************/
  130.  
  131. template <class Element>
  132. KPBag<Element>::operator KPList<Element>() const
  133. {
  134.     KPList<Element> list;
  135.  
  136.     KPReadOnlyIterator<KPBag<Element>::Slot> iter(my_list);
  137.     FOREACH (iter)
  138.         for (register int i=0; i<iter->my_count; i++)
  139.             list.add_to_tail(iter->my_element);
  140.  
  141.     return list;
  142. }
  143.  
  144. /****************************************************************************/
  145.  
  146. template <class Element>
  147. inline KPBag<Element>
  148. KPBag<Element>::operator+(const KPBag<Element> &bag) const
  149. {
  150.     KPBag<Element> new_bag(*this);
  151.     new_bag += bag;
  152.     return new_bag;
  153. }
  154.  
  155. /****************************************************************************/
  156.  
  157. template <class Element>
  158. inline KPBag<Element>
  159. KPBag<Element>::operator+(const Element &element) const
  160. {
  161.     KPBag<Element> new_bag(*this);
  162.     new_bag += element;
  163.     return new_bag;
  164. }
  165.  
  166. /****************************************************************************/
  167.  
  168. template <class Element>
  169. inline KPBag<Element> &
  170. KPBag<Element>::operator+=(const KPBag<Element> &bag)
  171. {
  172.     return add(bag);
  173. }
  174.  
  175. /****************************************************************************/
  176.  
  177. template <class Element>
  178. inline KPBag<Element> &
  179. KPBag<Element>::operator+=(const Element &element)
  180. {
  181.     return add(element, 1);
  182. }
  183.  
  184. /****************************************************************************/
  185.  
  186. template <class Element>
  187. KPBag<Element> &
  188. KPBag<Element>::add(const KPBag<Element> &bag)
  189. {
  190.     KPIterator<KPBag<Element>::Slot> a(my_list);
  191.     KPReadOnlyIterator<KPBag<Element>::Slot> b(bag.my_list);
  192.  
  193.     while (b.ptr()) {
  194.         while (a.ptr() && a->my_element < b->my_element)
  195.             a++;
  196.         if (!a.ptr()) {
  197.             for (; b.ptr(); b++)
  198.                 my_list.add_to_tail(*b);
  199.         }
  200.         else {
  201.             if (a->my_element == b->my_element) {
  202.                 a->my_count += b->my_count;
  203.                 a++;
  204.             }
  205.             else
  206.                 a.insert_before_current(*b);
  207.             b++;
  208.         }
  209.     }
  210.  
  211.     return *this;
  212. }
  213.  
  214. /****************************************************************************/
  215.  
  216. template <class Element>
  217. KPBag<Element> &
  218. KPBag<Element>::add(const Element &element, int num)
  219. {
  220.     if (num < 0) {
  221.         cerr << "KPBag - can't add a negative number of something\n";
  222.         exit(EXIT_FAILURE);
  223.     }
  224.  
  225.     else if (num > 0) {
  226.         KPIterator<KPBag<Element>::Slot> iter(my_list);
  227.  
  228.         // Start looking from the end of the list, in case the elements are
  229.         // being added in alphabetical order.
  230.  
  231.         iter.end();
  232.         while (iter.ptr() && element < iter->my_element)
  233.             --iter;
  234.         if (!iter.ptr()) {
  235.             KPBag<Element>::Slot slot(element, num);
  236.             my_list.add_to_head(slot);
  237.         }
  238.         else if (iter->my_element == element)
  239.             iter->my_count += num;
  240.         else {
  241.             KPBag<Element>::Slot slot(element, num);
  242.             iter.insert_after_current(slot);
  243.         }
  244.     }
  245.  
  246.     return *this;
  247. }
  248.  
  249. /****************************************************************************/
  250.  
  251. template <class Element>
  252. KPBag<Element>
  253. KPBag<Element>::operator-(const KPBag<Element> &bag) const
  254. {
  255.     KPBag<Element> new_bag;
  256.  
  257.     KPReadOnlyIterator<KPBag<Element>::Slot> a(my_list), b(bag.my_list);
  258.  
  259.     FOREACH(b) {
  260.         while (a.ptr() && a->my_element < b->my_element)
  261.             a++;
  262.         if (!a.ptr() || b->my_element < a->my_element ||
  263.                         b->my_count > a->my_count) {
  264.             cerr << "KPBag - error subtracting more than exists\n";
  265.             exit(EXIT_FAILURE);
  266.         }
  267.         else if (b->my_count < a->my_count) {
  268.             KPBag<Element>::Slot slot(a->my_element, a->my_count - b->my_count);
  269.             new_bag.my_list.add_to_tail(slot);
  270.         }
  271.         a++;
  272.     }
  273.  
  274.     return new_bag;
  275. }
  276.  
  277. /****************************************************************************/
  278.  
  279. template <class Element>
  280. inline KPBag<Element>
  281. KPBag<Element>::operator-(const Element &element) const
  282. {
  283.     KPBag<Element> new_bag(*this);
  284.     return new_bag.remove(element, 1);
  285. }
  286.  
  287. /****************************************************************************/
  288.  
  289. template <class Element>
  290. inline KPBag<Element> &
  291. KPBag<Element>::operator-=(const KPBag<Element> &bag)
  292. {
  293.     return remove(bag);
  294. }
  295.  
  296. /****************************************************************************/
  297.  
  298. template <class Element>
  299. inline KPBag<Element> &
  300. KPBag<Element>::operator-=(const Element &element)
  301. {
  302.     return remove(element, 1);
  303. }
  304.  
  305. /****************************************************************************/
  306.  
  307. template <class Element>
  308. KPBag<Element> &
  309. KPBag<Element>::remove(const KPBag &bag)
  310. {
  311.     if (this == &bag)
  312.         my_list.clear();
  313.  
  314.     else {
  315.         KPIterator<KPBag<Element>::Slot> a(my_list);
  316.         KPReadOnlyIterator<KPBag<Element>::Slot> b(bag.my_list);
  317.  
  318.         FOREACH(b) {
  319.             while (a.ptr() && a->my_element < b->my_element)
  320.                 a++;
  321.             if (!a.ptr() || b->my_element < a->my_element ||
  322.                             b->my_count > a->my_count) {
  323.                 cerr << "KPBag - error subtracting more than exists\n";
  324.                 exit(EXIT_FAILURE);
  325.             }
  326.             else if (b->my_count < a->my_count)
  327.                 a->my_count -= b->my_count;
  328.             else
  329.                 a.remove_current();
  330.             a++;
  331.         }
  332.     }
  333.  
  334.     return *this;
  335. }
  336.  
  337. /****************************************************************************/
  338.  
  339. template <class Element>
  340. KPBag<Element> &
  341. KPBag<Element>::remove(const Element &element, int num)
  342. {
  343.     KPIterator<KPBag<Element>::Slot> iter(my_list);
  344.  
  345.     while (iter.ptr() && iter->my_element < element)
  346.         iter++;
  347.  
  348.     if (!iter.ptr() || element < iter->my_element || num > iter->my_count) {
  349.         cerr << "KPBag - error subtracting more than exists\n";
  350.         exit(EXIT_FAILURE);
  351.     }
  352.     else if (num < iter->my_count)
  353.         iter->my_count -= num;
  354.     else
  355.         iter.remove_current();
  356.  
  357.     return *this;
  358. }
  359.  
  360. /****************************************************************************/
  361.  
  362. template <class Element>
  363. KPBag<Element> &
  364. KPBag<Element>::remove_all(const Element &element)
  365. {
  366.     KPIterator<KPBag<Element>::Slot> iter(my_list);
  367.  
  368.     while (iter.ptr() && iter->my_element < element)
  369.         iter++;
  370.     if (iter.ptr() && iter->my_element == element)
  371.         iter.remove_current();
  372.  
  373.     return *this;
  374. }
  375.  
  376. /****************************************************************************/
  377.  
  378. template <class Element>
  379. bool
  380. KPBag<Element>::operator==(const KPBag<Element> &bag) const
  381. {
  382.     if (this == &bag)
  383.         return true;
  384.     
  385.     if (my_list.size() != bag.my_list.size())
  386.         return false;
  387.  
  388.     KPReadOnlyIterator<KPBag<Element>::Slot> a(my_list), b(bag.my_list);
  389.     while (a.ptr()) {
  390.         if (!(a->my_count == b->my_count && a->my_element == b->my_element))
  391.             return false;
  392.         a++, b++;
  393.     }
  394.  
  395.     return true;
  396. }
  397.  
  398. /****************************************************************************/
  399.  
  400. template <class Element>
  401. inline bool
  402. KPBag<Element>::operator!=(const KPBag<Element> &bag) const
  403. {
  404.     return !operator==(bag);
  405. }
  406.  
  407. /****************************************************************************/
  408.  
  409. template <class Element>
  410. bool
  411. KPBag<Element>::operator<(const KPBag<Element> &bag) const
  412. {
  413.     if (bag.my_list.size() < my_list.size())
  414.         return false;
  415.     else if (my_list.size() < bag.my_list.size())
  416.         return true;
  417.     else {
  418.         KPReadOnlyIterator<KPBag<Element>::Slot> a(my_list), b(bag.my_list);
  419.         while (a.ptr()) {
  420.             if (b->my_count < a->my_count)
  421.                 return false;
  422.             else if (a->my_count < b->my_count)
  423.                 return true;
  424.             else if (b->my_element < a->my_element)
  425.                 return false;
  426.             else if (a->my_element < b->my_element)
  427.                 return true;
  428.             a++, b++;
  429.         }
  430.     }
  431.  
  432.     return false;
  433. }
  434.  
  435. /****************************************************************************/
  436.  
  437. template <class Element>
  438. inline KPBag<Element> &
  439. KPBag<Element>::operator=(const KPBag<Element> &bag)
  440. {
  441.     my_list = bag.my_list;
  442.     return *this;
  443. }
  444.  
  445. /****************************************************************************/
  446.  
  447. template <class Element>
  448. inline KPBag<Element> &
  449. KPBag<Element>::operator=(const Element &element)
  450. {
  451.     KPBag<Element>::Slot slot(element, 1);
  452.     my_list += slot;
  453.     return *this;
  454. }
  455.  
  456. /****************************************************************************/
  457.  
  458. template <class Element>
  459. KPBag<Element> &
  460. KPBag<Element>::operator=(const KPList<Element> &list)
  461. {
  462.     clear();
  463.     KPReadOnlyIterator<Element> iter(list);
  464.     FOREACH(iter)
  465.         add(*iter);
  466.  
  467.     return *this;
  468. }
  469.  
  470. /****************************************************************************/
  471.  
  472. template <class Element>
  473. KPList<Element>
  474. KPBag<Element>::list() const
  475. {
  476.     KPList<Element> list;
  477.  
  478.     KPReadOnlyIterator<KPBag<Element>::Slot> iter(my_list);
  479.     FOREACH(iter)
  480.         for (register int i=0; i<iter->my_count; i++)
  481.             list.add_to_tail(iter->my_element);
  482.  
  483.     return list;
  484. }
  485.  
  486. /****************************************************************************/
  487.  
  488. template <class Element>
  489. KPList<Element>
  490. KPBag<Element>::unique_list() const
  491. {
  492.     KPList<Element> list;
  493.  
  494.     KPReadOnlyIterator<KPBag<Element>::Slot> iter(my_list);
  495.     FOREACH(iter)
  496.         list.add_to_tail(iter->my_element);
  497.  
  498.     return list;
  499. }
  500.  
  501. /****************************************************************************/
  502.  
  503. template <class Element>
  504. int
  505. KPBag<Element>::size() const
  506. {
  507.     int total_count = 0;
  508.     KPReadOnlyIterator<KPBag<Element>::Slot> iter(my_list);
  509.     FOREACH(iter)
  510.         total_count += iter->my_count;
  511.     return total_count;
  512. }
  513.  
  514. /****************************************************************************/
  515.  
  516. template <class Element>
  517. inline int
  518. KPBag<Element>::unique_size() const
  519. {
  520.     return my_list.size();
  521. }
  522.  
  523. /****************************************************************************/
  524.  
  525. template <class Element>
  526. inline bool
  527. KPBag<Element>::is_empty() const
  528. {
  529.     return my_list.is_empty();
  530. }
  531.  
  532. /****************************************************************************/
  533.  
  534. template <class Element>
  535. bool
  536. KPBag<Element>::contains(const KPBag<Element> &bag) const
  537. {
  538.     if (this == &bag)
  539.         return true;
  540.  
  541.     KPReadOnlyIterator<KPBag<Element>::Slot> a(my_list), b(bag.my_list);
  542.  
  543.     while (b.ptr()) {
  544.         while (a.ptr() && a->my_element < b->my_element)
  545.             a++;
  546.         if (!(a.ptr() && a->my_element == b->my_element &&
  547.                          a->my_count >= b->my_count))
  548.             return false;
  549.         a++;
  550.         b++;
  551.     }
  552.  
  553.     return true;
  554. }
  555.  
  556. /****************************************************************************/
  557.  
  558. template <class Element>
  559. bool
  560. KPBag<Element>::contains(const Element &element, int num) const
  561. {
  562.     KPReadOnlyIterator<KPBag<Element>::Slot> iter(my_list);
  563.  
  564.     while (iter.ptr() && iter->my_element < element)
  565.         iter++;
  566.     return (iter.ptr() && iter->my_element == element && iter->my_count >= num);
  567. }
  568.  
  569. /****************************************************************************/
  570.  
  571. template <class Element>
  572. int
  573. KPBag<Element>::occurrences_of(const Element &element) const
  574. {
  575.     KPReadOnlyIterator<KPBag<Element>::Slot> iter(my_list);
  576.  
  577.     while (iter.ptr() && iter->my_element < element)
  578.         iter++;
  579.     if (iter.ptr() && iter->my_element == element)
  580.         return iter->my_count;
  581.     else
  582.         return 0;
  583. }
  584.  
  585. /****************************************************************************/
  586.  
  587. template <class Element>
  588. Element
  589. KPBag<Element>::retrieve()
  590. {
  591.     if (my_list.is_empty()) {
  592.         cerr << "KPBag: retreive() - bag empty\n";
  593.         exit(EXIT_FAILURE);
  594.     }
  595.  
  596.     Element element = my_list.head().my_element;
  597.     if (--my_list.head().my_count == 0)
  598.         my_list.remove_head();
  599.     return element;
  600. }
  601.  
  602. /****************************************************************************/
  603.  
  604. template <class Element>
  605. inline KPBag<Element> &
  606. KPBag<Element>::clear()
  607. {
  608.     my_list.clear();
  609.     return *this;
  610. }
  611.  
  612. /****************************************************************************/
  613.  
  614. #endif /* KP_BAG_DEFINED */
  615.